P5929 [POI1999]地图

至少有一半不小于 A(k)A(k) , 至少有一半不大于 A(k)A(k)

所以 A(k)A(k) 应该是选出的区域人口的中位数。

为了使误差尽可能小,每次应该取排序后连续的一段区间染相同颜色。

dpi,jdp_{i,j} 表示使用前 ii 种颜色,将前 jj 个区域染色的最小误差,val(l,r)\text{val(l,r)} 表示将 [l,r][l,r] 染成一个颜色的误差。

那么有:

dpi,j=min{dpi1,k1+val(k,j)}(1kj)dp_{i,j}=\min\{ dp_{i-1,k-1} + \text{val}(k,j) \} (1 \le k \le j)

val(l,r)\text{val}(l,r) 可以分类讨论中位数的值,分成 小于中位数 和 大于中位数 两种情况计算。

这道题中位数好像取不取小数都能过。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long

const int MAXN = 3000 , MAXM = 10;
int n , m , a[ MAXN + 5 ];
LL Suma[ MAXN + 5 ]; double dp[ MAXM + 5 ][ MAXN + 5 ];

double Val( int l , int r ) {
    int Mid = ( l + r ) >> 1;
    if( ( r - l + 1 ) % 2 ) { //l   Mid    r
        double Mida = a[ Mid ];
        return ( Suma[ r ] - Suma[ Mid - 1 ] - Mida * ( r - Mid + 1 ) ) + ( Mida * ( Mid - l ) - ( Suma[ Mid - 1 ] - Suma[ l - 1 ] ) );
    }
    else { //l   Mid Mid+1    r
        double Mida = ( a[ Mid ] + a[ Mid + 1 ] ) / 2.0;
        return ( Suma[ r ] - Suma[ Mid ] - Mida * ( r - Mid ) + Mida * ( Mid - l + 1 ) - ( Suma[ Mid ] - Suma[ l - 1 ] ) );
    }
}
int main( ) {
    scanf("%d %d",&n,&m);
    for( int i = 1 ; i <= n ; i ++ ) scanf("%d", &a[ i ] );
    sort( a + 1 , a + n + 1 );
    for( int i = 1 ; i <= n ; i ++ ) Suma[ i ] = Suma[ i - 1 ] + a[ i ];

    for( int i = 0 ; i <= m ; i ++ ) for( int j = 0 ; j <= n ; j ++ ) dp[ i ][ j ] = 1e15;

    dp[ 0 ][ 0 ] = 0;
    for( int i = 1 ; i <= m ; i ++ )
        for( int j = 1 ; j <= n ; j ++ )
            for( int k = 1 ; k <= j ; k ++ )
                dp[ i ][ j ] = min( dp[ i ][ j ] , dp[ i - 1 ][ k - 1 ] + Val( k , j ) );
    printf("%.0f\n", dp[ m ][ n ] );
    return 0;
}